package hot100;

public class Solution474 {
    public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i < strs.length; i++) {
            int one = getSum(strs[i]);
            int zero = strs[i].length() - one;
            for (int j = m; j >= zero; j--) {
                for (int k = n; k >= one; k--) {
                    dp[j][k] = Math.max(dp[j][k], dp[j - zero][k - one] + 1);
                }
            }
        }
        return dp[m][n];
    }

    public int getSum(String str) {
        int sum = 0;
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '1') {
                sum++;
            }
        }
        return sum;
    }

    public static void main(String[] args) {
        Solution474 solution474 = new Solution474();
        System.out.println(solution474.findMaxForm(new String[]{"10", "1", "0"}, 1, 1));
    }
}
